Problem statement: zenit14skh

Súčasťou únikového plánu je ukradnutie vysielačky bezpečnostnej služby. Bezpečnostná služba sídli v budove, ktorá má \(N\) poschodí. Na jej najvrchnejšom poschodí je komunikačná centrála. Tu sa nachádza vysielačka, ktorú treba ukradnúť a dopraviť na zem. Najvhodnejší na túto úlohu je orol Marián, ktorý je dostatočne rýchly na bleskovú krádež a zároveň dostatočne silný na udržanie vysielačky.

Po uchopení vysielačky Marián vyletí z komunikačnej centrály, zníži svoju letovú výšku a pustí vysielačku na zem. Našou úlohou je zistiť, ako najvyššie môže byť Marián v čase, keď pustí vysielačku, ak chceme, aby sa nerozbila. Zvieratká ju totiž budú potrebovať na oklamanie stráží. Na druhej strane, Marián nemôže priletieť príliš nízko, pretože stratí čas.

Letové výšky si označíme podľa úrovní poschodí číslami 1 až \(N\). Ak pre nejakú výšku vysielačka prežije, potom prežije pri každom páde z danej výšky (zanedbáme všetky faktory ovplyvňujúce výsledok experimentu okrem výšky). Ak nejakú výšku vysielačka neprežije, potom neprežije ani žiadnu vyššiu. Z intervalu 1 až \(N\) existuje aspoň jedna výška taká, že to vysielačka prežije.

Zvieratká by radi poznali túto výšku ešte predtým, ako prebehne akcia na ostro. Na tieto účely majú \(X\) nefunkčných, ale stále nerozbitých vysielačiek. Zvieratká budu opakovať nasledovný experiment: Marián vyletí do nejakej výšky a pustí vysielačku na zem. Tá dopadne a buď sa rozbije alebo nerozbije. Na základe tejto informácie môžu zvieratká uskutočniť ďalší experiment s inou výškou. Ak sa vysielačka nerozbije, môže sa použiť v ďalšom experimente. Ak sa rozbije, už je nanič.

Hlavným cieľom je presne identifikovať hľadanú výšku – experimenty musia byť robené tak, aby sa to bez ohľadu na ich výsledok podarilo. Na druhej strane, na konci nám nemusia ostať nerozbité žiadne pokusné vysielačky: na tom, či sa rozbijú alebo nie nám nezáleží. Napíšte program, ktorý pre dané \(N\) a \(X\) vypočíta najmenší nutný počet experimentov.

Napríklad, ak máme jednu vysielačku a budova má tri poschodia, nemôžeme začať zhodením vysielačky z tretieho poschodia. Ak by sa totiž rozbila, nevieme, či by prežila pád z druhého poschodia alebo nie. A nemáme už žiadnu inú vysielačku na ďalší experiment. Preto musíme začať zhodením vysielačky z druhého poschodia. Ak neprežije, vieme, že najvyššia povolená výška je 1 (z prvého poschodia vysielačka vďaka definícii problému v predchádzajúcom texte vždy prežije). Ak prežije, vyskúšame ešte tretie poschodie a podľa výsledku tohto experimentu bude odpoveď 2 alebo 3 (nevadí, ak sa nám rozbije, lebo odpoveď už budeme vedieť).

Formát vstupu a výstupu

Na vstupe sú dve medzerou oddelené čísla \(N\) a \(X\). Platí \(2 \leq N \leq 1,000\) a \(1\leq X\leq 6\). Na výstup vypíšte najmenší počet experimentov, ktorý bude stačiť na určenie požadovanej výšky.

Uvedomme si, že podľa výsledku prvého experimentu môžeme určovať výšky nasledujúceho experimentu a tak ďalej. V niektorých vývojoch nám stačí menej experimentov, v niektorých viac. Pre daný vstup nás zaujíma, koľko najmenej experimentov bude určite stačiť bez ohľadu na hodnotu výslednej výšky pri rozumnej stratégii. Dobrá rada: Za riešenie, ktoré pri výpočte ignoruje počet vysielačiek, veľa bodov na ostrom testovaní nebude.

Príklady

Input:

3 1

Output:

2

Toto je príklad zo zadania. Neexistuje stratégia, ktorá by nám zaručene priniesla výsledok na jeden experiment.

Input:

7 2

Output:

3

Jedna zo stratégií je nasledovná: Skúsime prvý experiment z výšky 4. Ak sa vysielačka rozbije, skúsime pomocou druhej vysielačky výšku 2. Ak sa rozbije aj tá, vieme, že odpoveď je 1. V opačnom prípade tretím experimentom (pomocou vysielačky, ktorá prežila pád z výšky 2) skúsime výšku 3 a podľa výsledku prehlásime za odpoveď 2 alebo 3. Ak sa vysielačka v prvom experimente z výšky 4 nerozbije, zostali nám dve vysielačky a pomocou dvoch experimentov vieme zistiť, či je odpoveď 4, 5, 6 alebo 7.

Input:

339 5

Output:

9